// @algorithm @lc id=225 lang=cpp 
// @title implement-stack-using-queues

#define print(...)
#define queue_t list
class MyStack {
public:
    int out;
    vector<queue_t<int>> q;
    /** Initialize your data structure here. */
    MyStack():out(0){
        q.reserve(2);
        q.assign(2, queue_t<int>());
    }

    void tryOut(){
        while(q[1-out].size()>1) {
            q[out].push_back(q[1-out].front());
            q[1-out].pop_front();
        }
        out = 1 - out;
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        q[1-out].push_back(x);
        print("push(", x, ")|", out, "|", q, "\n")
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        tryOut();
        auto data = q[out].front();
        q[out].pop_front();
        print("pop()=", data,"|", out, "|", q, "\n")
        return data;
    }
    
    /** Get the top element. */
    int top() {
        tryOut();
        auto data = q[out].front();
        q[1-out].push_back(data);
        q[out].pop_front();
        print("top()=", data, "|", out, "|", q, "\n")
        return data;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        print("empty()=", q[1-out].empty() && q[out].empty(), "|", out, "|", q, "\n")
        return q[1-out].empty() && q[out].empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */